# T1 一个数组中某个元素可能出现了一半以上，找出这个数
# 时间复杂度 O(n)
# 空间复杂度 O(1)


# T1 无重复数组的全排列
from typing import List


# 数组元素的全排列
class Solution:
    def func(self, nums: List):
        temp = [m for m in nums]
        result = []
        def dfs(x):
            if x == len(nums) - 1:
                result.append(list(temp))
                return
            t = set()
            for i in range(x, len(temp)):
                # 用去元素重复时剪枝
                if temp[i] in t:
                    continue
                t.add(temp[i])
                temp[i], temp[x] = temp[x], temp[i]
                dfs(x + 1)
                temp[i], temp[x] = temp[x], temp[i]
        dfs(0)
        return result


# 字符串的全排列
class Solution_s:
    def permutation(self, s: str) -> List[str]:
        c, result = list(s), []

        def dfs(inx):
            if inx == len(c) - 1:
                result.append(''.join(c))  # 添加排列方案
                return
            dic = set()
            for i in range(inx, len(c)):
                if c[i] in dic:
                    continue  # 重复，因此剪枝
                dic.add(c[i])
                c[i], c[inx] = c[inx], c[i]  # 交换，将 c[i] 固定在第 x 位
                dfs(inx + 1)  # 开启固定第 x + 1 位字符
                c[i], c[inx] = c[inx], c[i]  # 恢复交换
        dfs(0)
        return result


if __name__ == '__main__':
    nums = [1, 2, 3]
    s = 'abc'

    t1 = Solution()
    print(t1.func(nums))

    t2 = Solution_s()
    print(t2.permutation(s))
